/* Copyright (c) 2010, mitsuhisa.net
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above
 *       copyright notice, this list of conditions and the following
 *       disclaimer in the documentation and/or other materials provided
 *       with the distribution.
 *     * Neither the name of the misuhisa.net nor the names of its
 *       contributors may be used to endorse or promote products derived
 *       from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef NYU_HASH_HPP_
#define NYU_HASH_HPP_

#include <cstring>

namespace nyu {

template<typename Key, typename Val>
class Hash {
public:
    typedef unsigned int code_type;

    Hash(size_t nents = INITIAL_NENTS) :
            ents_(new Entry*[nents]), nents_(nents), size_(0) {
        ::memset(ents_, 0, sizeof(Entry*) * nents);
    }

    ~Hash() {
        for (int i = 0, j = nents_; i < j; i++) {
            delete ents_[i];
        }
        delete[] ents_;
    }

    size_t size() const {
        return size_;
    }

    template<typename Func>
    void put(Key key, Val value, Func fn) {
        code_type h = fn(key);
        size_t hh = h % nents_;
        int depth = 0;

        Entry* ent = ents_[hh];
        while (ent && !fn(ent->key, key)) {
            ent = ent->next;
            ++depth;
        }

        if (ent) {
            ent->value = value;
            return;
        }

        ents_[hh] = new Entry(key, value, ents_[hh]);
        ++size_;

        if (depth > 2)
            rehash(fn);
    }

    template<typename Func>
    bool get(Key key, Val& value, Func fn) {
        code_type h = fn(key);

        Entry* ent = ents_[h % nents_];
        while (ent && !fn(ent->key, key)) {
            ent = ent->next;
        }

        if (ent) {
            value = ent->value;
            return true;
        }

        return false;
    }

    template<typename Func>
    void eachKeys(Func fn) {
        Entry** ents = ents_;

        for (size_t i = 0, j = nents_; i < j; i++) {
            for (Entry* ent = ents[i]; ent; ent = ent->next) {
                fn(ent->key);
            }
        }
    }

private:
    template<typename Func>
    void rehash(Func fn) {
        size_t new_size, i, j;
        Entry **new_ents, *ent, **ents;

        new_size = nents_ * 2 + 1;

        new_ents = new Entry*[new_size];

        ::memset(new_ents, 0, sizeof(Entry*) * new_size);

        ents = ents_;
        for (i = 0, j = nents_; i < j; i++) {
            for (ent = ents[i]; ent;) {
                Entry* tmp = ent;
                size_t h = fn(tmp->key) % new_size;
                ent = ent->next;
                tmp->next = new_ents[h];
                new_ents[h] = tmp;
            }
        }

        delete[] ents;

        nents_ = new_size;
        ents_ = new_ents;
    }

    struct Entry {
        Key key;
        Val value;
        Entry* next;

        Entry(Key k, Val v, Entry* n = 0) : key(k), value(v), next(n) {
        }

        ~Entry() {
            Entry* e = next;
            while (e) {
                Entry* n = e->next;
                e->next = 0;

                delete e;

                e = n;
            }
        }
    };

    Entry** ents_;
    size_t nents_;
    size_t size_;

    static const int INITIAL_NENTS = 7;
};

}

#endif /* NYU_HASH_HPP_ */
